1. Field of the Invention
The present invention relates to physical synthesis and in particular to interconnect-driven physical synthesis using persistent virtual routing.
2. Related Art
In modern process technologies, accurately predicting interconnect delays has become one of the critical steps in high performance integrated circuit (IC) designs. Notably, in the 65 nm regime and beyond, interconnect delays can change dramatically depending on the routing topology and layer assignment. As a result, the pin-to-pin delays and parasitics of a net estimated from a virtual router during circuit optimization at the pre-route stage may be very different from its actual delay after routing.
This difference in pin-to-pin delays and parasitics may significantly mislead the circuit optimization trajectory, e.g. leading to wasted over-optimization effort (during pre-routing optimization) on nets that are not really critical. Additionally, truly critical nets may be left un-optimized by circuit optimization steps applied during the pre-route stage, thereby requiring expensive optimization steps during post-route optimization (which tends to be considerably less flexible than pre-route optimization). As a result, design convergence becomes difficult due to this unpredictability in the design flow and often leads to ICs with inferior performance.
During the last decade, the fanout-based wireload models used by traditional synthesis have been augmented with placement-based models for the delays and parasitics of the nets as part of the widespread adoption of physical synthesis. Early physical synthesis techniques used simple half-rectangle perimeter (HRPM) based wirelength estimates for the nets during circuit optimization at the pre-route stage. However, although the HRPM metric is an exact measure for the minimum wirelength of a net that contains two or three pins, it may significantly underestimate even the best possible wirelength required to route a multi-pin net.
As wire delays became more significant (largely a result of process scaling), this weakness of simple HRPM-based wire length estimation was rectified with empirical fanout compensation factors. Unfortunately, even this enhancement failed to provide good estimates for driver-to-sink wirelengths or side-load parasitics for multi-pin nets. As a result, the use of virtual routers gained widespread acceptance for the purpose of wire delay estimation. These virtual routers ranged from simple greedy tree topology generation schemes to more sophisticated heuristics.
An exemplary virtual router uses Steiner trees, wherein given a set of points (vertices), the length of interconnect connecting such points can be minimized by adding one or more intermediate vertices. For example, FIG. 1A illustrates a routing generated by a virtual router (without the use of Steiner trees) in which a driver 101 drives cells 102, 103, and 104 using interconnect 105, 106, and 107. In contrast, FIG. 1B illustrates a Steiner tree based routing generated by a virtual router in which driver 101 drives cells 102, 103, and 104 using interconnect 108. Even though Steiner trees can provide a better approximation of the actual topologies generated by global routers, they still suffer from several problems that gradually became more serious with the poor scaling of wire delays.
Note that because topology generation by a virtual router of the kind described above is oblivious to congestion, routing estimates can represent minimal wire lengths. Specifically, these routing estimates fail to model the effect of routing detours on the parasitics and delays of the nets. Early efforts to tackle this problem relied on blockage-aware route embeddings to capture the detours caused by hard macros. For example, FIG. 1C illustrates a driver 120 driving a cell 121 using an interconnect 124. However, because of congestion in the narrow channel between the macros 122 and 123, driver 120 may drive cell 121 using interconnect 125, which is considerably longer than interconnect 124. A global router can be used to generate an approximate congestion map once the placement is stabilized. This congestion map can then be used by the subsequent net topology generation algorithms. Unfortunately, this technique has significant computation cost.
Early Steiner-based wire delay estimation schemes attempted to capture the complexities of layer assignment by relying on average layer parasitics. Although this averaging sufficed in early process technologies in which the wire delays were comparatively small, the lack of accurate layer and via modeling can result in large estimation errors in modern designs in which vias can be highly resistive and variable, and different metal layers can yield vastly different delays. Referring to FIGS. 1D and 1E, driver 130 drives cell 131 via one of interconnects 132 or 133, respectively. Interconnect 132 and 133 are the same length, but are formed in different layers and therefore can result in different delays. For example, an RC delay for a 1 mm long copper wire at the 68 nm node can vary from 209 ps to 767 ps depending on its layer. In general, the propagation delay for long wires is significantly higher when routed in a lower metal layer than when routed in an upper metal layer. Unfortunately, virtual routers are ill-equipped to predict which layer will ultimately be used for any particular wire.
Note that in the case of a relatively long wire, significantly more buffers may be needed on the lower metal layer compared to the upper metal layer. In fact, in general, the different routing paths shown in FIGS. 1A, 1B, 1C, 1D, and 1E can also result in a different number of buffers needed to drive the routing paths, different sizes for such buffers, and different sizes of the sink gates associated with such buffers. All of the foregoing undesirably causes additional congestion, potential re-routing, and overall greater uncertainty in the placement process.
The problematic divergence of routing estimates (which is in part caused because of the topology generation algorithms used by the virtual router for estimation purposes being significantly different from those used by the actual global routers) can be partly solved by using a fast global router for the estimation of routing topologies during the placement stage itself. That is, the same topology generation algorithms can be used for estimation and for routing. Unfortunately, even though this technique can accurately model layer-specific congestion and vias, it also has significant computation overhead.
Yet further, the topology generated by the global router for any given net can be very different from the one that had been used for its delay estimation. That is, a global router may generate very different topologies for the same net in response to small differences in the congestion map. This problem could conceivably be resolved by guaranteeing the routes used for estimation by fixing their routes when first generated, and then treating them as pre-routed nets subsequently. However, this simple approach is impractical because of several reasons. First, generating high quality congestion-aware routes for all the nets during placement-based circuit optimization is prohibitively expensive. Second, as the circuit optimization proceeds, previously-generated routes become invalid because of buffering, logic restructuring, changes in cell sizes and/or cell placement. Third, even if the routes are generated in a congestion-aware manner, fixing even a significant fraction of the nets has a huge impact on route completion during the final global routing phase due to the restrictions it places on the rip-up-and-reroute engine (that is not allowed to modify these pre-routed nets).
Therefore, a need arises for improved techniques that can cost-effectively take into account accurate delay and parasitic estimates in the placement stage.